/*
 * @Author: szx
 * @Date: 2022-06-30 13:50:14
 * @LastEditTime: 2022-06-30 13:55:11
 * @Description:
 * @FilePath: \leetcode\1100-1199\1175\1175.js
 */
/**
 * @param {number} n
 * @return {number}
 */
const MOD = 1000000007;
var numPrimeArrangements = function (n) {
    let numPrimes = 0;
    // 先找出1-n的所有质数
    for (let i = 2; i <= n; i++) if (isPrime(i)) numPrimes++;
    // 然后组合，总的方案数即为「所有质数都放在质数索引上的方案数」×「所有合数都放在合数索引上的方案数」
    let res = 1;
    let m = n - numPrimes;
    while (numPrimes > 0) {
        res = res % MOD;
        res *= numPrimes;
        numPrimes--;
    }
    while (m > 0) {
        res = res % MOD;
        res *= m;
        m--;
    }
    return res;
};

const isPrime = (n) => {
    if (n === 1) return false;
    for (let i = 2; i * i <= n; i++) if (n % i === 0) return false;
    return true;
};
